Advances in wireless communication have enabled an increasing number of devices to wirelessly communicate with one another. In addition to mobile devices and computers, other devices such as headsets, microphones, remote controls, and televisions wirelessly communicate with one another. While wireless communication takes many forms, it often involves use of a channel within a frequency spectrum, typically referred to as a “radio frequency.” Certain frequency spectrums are reserved for specific types of communication. Other frequency spectrums (for example the White-Space spectrum in the ultra high frequency television (UHF-TV) bands) give priority to certain types of devices and communications (i.e. so-called primary users) but allow others (secondary users) to communicate on channels that are not currently in use by any primary user.
In many cases, two communication devices have multiple channels to choose from for communication. Here, a channel is defined as a part of the frequency spectrum, i.e., a center frequency and a channel width. For various reasons, it is possible that some of the channels may not be available (or open) at one or more of the communicating devices, thus preventing such a device to transmit on this channel or communicate effectively on it. For example, this can be due to legal requirements in the white-space spectrum in case a primary user is using this channel. Also, a channel may be very busy with other traffic.
The problem is that in many cases, two wireless devices want to communicate with one another, but the channels each of them has available for communication may be different. Some channels may be available at both devices, whereas other channels may only be available at one of the devices, while still others may not be available at any of the devices. The difficulty is that a-priori, neither of the devices has knowledge about which of the channels are available at the respective other device that it wants to communicate with. It only knows about the available channels at its own location, not about those at the location of the other device. In addition, in certain cases a channel may not allow communication even if it appears available for both devices, due to interferences that cannot be detected locally.
To “discover” each other, i.e., set up a reliable communication, wireless devices may utilize a protocol. Discovery is achieved when the devices communicate on some channel that is available at both devices and in an environment between the devices at the same time. In this case, the two nodes can use existing, standard protocols to set up any design communication protocol. They can either stay on the channel on which discovery occurred, or they may select any other channel based on any existing channel selection protocol.
The difficulty arises that the above discovery process should occur as quickly as possible; i.e., two or more devices should be able to find each other on an available channel quickly in order to avoid losing time (and energy). The problem is that if not done cleverly, the discovery time (=the time until two or more nodes discover each other) grows linearly in the total number of channels, which may be large. This is for example the case in the simple strategy in which the two devices periodically pick random channels until they happen to pick the same channel at the same time. Such random selection can thus consume significant user time and device energy.